package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
 * 示例:
 * <p>
 * A = [1, 2, 3, 4]
 * <p>
 * 返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
 * <p>
 * 1,2,3,5,7
 *
 * @author caijinnan
 * @date 2020/3/25 15:52
 */
public class 等差数列划分 {
    @Test
    public void run() {
        int[] nums = {1, 2, 3, 4, 5, 10};
        System.out.println(numberOfArithmeticSlices(nums));
    }

    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length <= 2) {
            return 0;
        }
        int[] subNums = new int[nums.length - 1];
        for (int i = 0; i < subNums.length; i++) {
            subNums[i] = nums[i + 1] - nums[i];
        }
        int lastNum = subNums[0];
        int length = 2;
        int sum = 0;
        for (int i = 1; i < subNums.length; i++) {
            if (subNums[i] == lastNum) {
                length++;
                if (i != subNums.length - 1) {
                    continue;
                }
                if (length >= 3) {
                    sum += (length - 1) * (length - 2) / 2;
                    break;
                }
            }
            if (length >= 3) {
                sum += (length - 1) * (length - 2) / 2;
            }
            lastNum = subNums[i];
            length = 2;
        }
        return sum;
    }
}
